package com.ln.prac.base.m202206.d13;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 *
 * @Author zhangj
 * @Date 2022/6/12 22:59
 */
public class SortTest {


//    public static List<Integer> fastSort(List<Integer> list) {
//        if(list.size() <= 0) {
//            return list;
//        }
//        Integer num = list.get(0);
//        var left = list.stream().filter(x->x < num).collect(Collectors.toList());
//        var middle = list.stream().filter(x-> x.equals(num)).collect(Collectors.toList());
//        var right = list.stream().filter(x->x > num).collect(Collectors.toList());
//
//        left = fastSort(left);
//        right = fastSort(right);
//
//        left.addAll(middle);
//        left.addAll(right);
//        return left;
//    }

    public static void fastSort2(Integer[] arr) {
        fastSort2(arr, 0, arr.length);
    }

    public static void fastSort2(Integer[] arr, int l, int r) {
        if(r - l <= 1) {
            return;
        }

        int mid = partition(arr, l , r);

        fastSort2(arr, l, mid);
        fastSort2(arr, mid + 1, r);

        merge(arr, l , mid, r);
    }

    private static void merge(Integer[] arr, int l, int mid, int r) {
        Integer[] B = Arrays.copyOfRange(arr, l, mid + 1);
        Integer[] C = Arrays.copyOfRange(arr, mid, r + 1);

        B[B.length - 1] = C[C.length - 1] = Integer.MAX_VALUE;

        int i = 0, j = 0;

        for (int k = l; k < r; k++) {
            if(B[i] < C[j]) {
                arr[k] = B[i++];
            } else {
                arr[k] = C[j++];
            }
        }
    }

    private static int partition(Integer[] arr, int l, int r) {
        int x = arr[l];
        int i = l + 1;
        int j = r;

        // x |--left--|--mid--|--right--|
        while (i != j) {
            if(arr[i] < x) {
                ++i;
            } else {
                swap(arr, i, --j);
            }
        }
        swap(arr, i - 1, l);
        return i - 1;
    }

    public static void swap(Integer[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        Integer[] sort2 = new Integer[]{5,3,2,4,6,7,8,10,2,33,34};

//        System.out.println(fastSort(Arrays.asList(sort2)));


        fastSort2(sort2);
        System.out.println(Arrays.asList(sort2));
    }

}
